package Exercise;

import java.util.Scanner;

public class demo17 {
    /**完全背包问题
     *
     * //注释部分是优化后的
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] v = new int[1001];
        int [] w = new int[1001];
        int [][] f = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for (int i = 1; i <=n ; i++) {
            for (int j = 0; j <=m ; j++) {
                for (int k = 0; k * v[i] <=j ; k++) {//优化后这一层循环去掉
                    f[i][j] = Math.max(f[i][j],f[i-1][j-v[i] * k]+ k * w[i]);//替换成下面的
                    // f[i][j] = f[i-1][j];
                    // if(j>=v[i]) f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
        sc.close();
    }
}
